#include <iostream>
using namespace std;

struct node
{
	char c;
	node *left;
	node *right;
};

//mh is not necessary
node* restoreTree(char pre[], int pl, int ph, char mid[], int ml, int mh)
{
	if(pl > ph)
		return NULL;
	char rootChar = pre[pl];
	int m;
	for(m=ml; m<=mh; m++)
	{
		if(mid[m] == rootChar)
			break;
	}
	node *rootNode = new node();
	rootNode->c = rootChar;
	rootNode->left = restoreTree(pre, pl+1, pl+m-ml, mid, ml, m-1);
	rootNode->right = restoreTree(pre, pl+m-ml+1, ph, mid, m+1, mh);
	return rootNode;
}

//mh is not necessary
node* restoreTree2(char pos[], int pl, int ph, char mid[], int ml, int mh)
{
	if(pl > ph)
		return NULL;
	char rootChar = pos[ph];
	int m;
	for(m=ml; m<=mh; m++)
	{
		if(mid[m] == rootChar)
			break;
	}
	node *rootNode = new node();
	rootNode->c = rootChar;
	rootNode->left = restoreTree2(pos, pl, pl+m-ml-1, mid, ml, m-1);
	rootNode->right = restoreTree2(pos, pl+m-ml, ph-1, mid, m+1, mh);
	return rootNode;
}

void print_pre(node* root)
{
	if(root)
	{
		cout << root->c << " ";
		print_pre(root->left);
		print_pre(root->right);
	}
}

void print_mid(node* root)
{
	if(root)
	{
		print_mid(root->left);
		cout << root->c << " ";
		print_mid(root->right);
	}
}

void print_pos(node* root)
{
	if(root)
	{
		print_pos(root->left);
		print_pos(root->right);
		cout << root->c << " ";
	}
}

int main()
{
	char pre[6] = {'a','b','d','c','e','f'};
	char mid[6] = {'d','b','a','e','c','f'};
	char pos[6] = {'d','b','e','f','c','a'};
	node* root = restoreTree(pre, 0, 5, mid, 0, 5);
	node* root2 = restoreTree2(pos, 0, 5, mid, 0, 5);
	print_pre(root);	
	cout << endl;
	print_mid(root);
	cout << endl;
	print_pos(root2);
	return 0;
}
